package de.mmis.core.sexpression;

import java.io.ByteArrayInputStream;
import java.io.ByteArrayOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.util.ArrayList;

import org.apache.log4j.Logger;

import de.mmis.core.base.Toolbox;
import de.mmis.core.base.abstracttree.InnerNode;
import de.mmis.core.base.abstracttree.LeafNode;
import de.mmis.core.base.abstracttree.LeafNode.Encoding;
import de.mmis.core.base.abstracttree.Tree;
import de.mmis.core.base.abstracttree.TreeParser;
import de.mmis.core.base.abstracttree.TreeParserException;

/**
 * This class is providing static methods to read an S-Expression from an input
 * stream or byte array
 * 
 * @author Christian Koch
 * 
 */
public class SExpressionParser implements TreeParser {

	private final static Logger LOGGER = Logger
			.getLogger(SExpressionParser.class);

	/**
	 * parses an S-Expression from a string encoded using UTF-8
	 * 
	 * @param data
	 *            string to parse
	 * @return resulting S-Expression
	 * @throws TreeParserException
	 *             an error occurred while parsing
	 */
	public static Tree parseUTF8(String data) throws TreeParserException {
		return parse(Toolbox.toUTF8Bytes(data));
	}

	/**
	 * parses an S-Expression from a byte array
	 * 
	 * @param data
	 *            byte array to parse
	 * @return resulting Tree
	 * @throws TreeParserException
	 *             an error occurred while parsing
	 */
	public static Tree parse(byte[] data) throws TreeParserException {
		try {
			return parse(new ByteArrayInputStream(data), false);
		} catch (IOException e) {
			LOGGER.error("unexpected IOException while writing to byte array",
					e);
		}
		return null;
	}

	/**
	 * parses an S-Expression from an input stream
	 * 
	 * @param in
	 *            input stream to parse
	 * @param lineBased
	 *            a newline character (\n or \r\n) is expected after reading an
	 *            S-Expression. a warning is printed to stderr, if it is not
	 *            present
	 * @return resulting Tree
	 * @throws TreeParserException
	 *             an error occurred while parsing
	 * @throws IOException
	 *             Exception while reading from input stream
	 */
	public static Tree parse(InputStream in, boolean lineBased)
			throws TreeParserException, IOException {
		UndoInputStream uin;
		if (!(in instanceof UndoInputStream))
			uin = new UndoInputStream(in);
		else
			// if in is already an UndoInputStream don't wrap it again
			uin = (UndoInputStream) in;

		int c = uin.read();
		if (c == -1)
			throw new TreeParserException("End of Stream while no data read",
					true, true);
		uin.undo();
		Tree result = parseInternal(uin);
		if (lineBased) {
			c = uin.read();
			if (c != -1 && c != '\n' && (c != '\r' || uin.read() != '\n'))
				LOGGER.warn("line based S-Expression "
						+ result
						+ " didn't end with a LF or a CR LF as expected (it actually ended with '"
						+ ((char) c) + "')");
		}
		return result;
	}

	/**
	 * internal; parses an S-Expression from an UndoInputStream
	 * 
	 * @param in
	 *            input stream to parse
	 * @return resulting Tree
	 * @throws TreeParserException
	 *             an error occurred while parsing
	 * @throws IOException
	 *             Exception while reading from input stream
	 */
	private static Tree parseInternal(UndoInputStream in)
			throws TreeParserException, IOException {
		skipWhitespaces(in);
		int c = in.read();
		if (c == '(') {
			skipWhitespaces(in);
			InnerNode struct = new InnerNode();
			while (in.peek() != ')') {
				Tree exp = parseInternal(in);
				struct.add(exp);
				skipWhitespaces(in);
			}
			in.read(); // read ')'
			return struct;
			// } else if (c == '{') // re-parse base64 encoded data
			// {
			// byte[] temp = decodeBase64(readBase64(in));
			// if (in.read() != '}')
			// throw new TreeParserException(
			// "Illegal character in Base64 encoded data");
			// return SExpressionParser.parse(temp);
		}
		// else {
		// LeafNode hint = null;
		/*
		 * if (c == '[') { skipWhitespaces(in); hint = parseAtom(in);
		 * 
		 * skipWhitespaces(in); if (in.read() != ']') throw new
		 * TreeParserException("Illegal display hint"); skipWhitespaces(in); }
		 * else
		 */if (c == -1)
			throw new TreeParserException("unexpected end of input stream",
					true, false);

		in.undo();
		LeafNode at = parseAtom(in);
		// if (hint != null) {
		// ignore display hints as they are not used in abstract trees
		// at.setDisplayHintData(hint.getData());
		// at.setDisplayHintEncoding(hint.getEncoding());
		// }
		return at;
		// }
	}

	/**
	 * internal, auxiliary; parses an atomic S-Expression from an
	 * UndoInputStream
	 * 
	 * @param in
	 *            input stream to parse
	 * @return resulting atomic Tree
	 * @throws TreeParserException
	 *             an error occurred while parsing
	 * @throws IOException
	 *             Exception while reading from input stream
	 */
	private static LeafNode parseAtom(UndoInputStream in) throws IOException,
			TreeParserException {
		ByteArrayOutputStream baos = new ByteArrayOutputStream();
		Encoding encoding = parseAtom(in, baos);
		return new LeafNode(baos.toByteArray(), encoding);
	}

	/**
	 * parses an atomic S-Expression from an UndoInputStream and writes data to
	 * OutputStream
	 * 
	 * @param in
	 *            input stream to parse
	 * @param out
	 *            output stream to write byte data to
	 * @return Encoding of atomic S-Expression read
	 * @throws TreeParserException
	 *             an error occurred while parsing
	 * @throws IOException
	 *             Exception while reading from input stream or writing to
	 *             output stream
	 */
	public static Encoding parseAtom(UndoInputStream in, OutputStream out)
			throws IOException, TreeParserException {
		int c = in.read();
		if (c == '\"') {
			decodeQuoted(in, out);
			return Encoding.Quoted;
		} else if (c == '#') {
			decodeHex(in, out);
			return Encoding.Hex;
		} else if (c == '|') {
			decodeBase64(in, out);
			return Encoding.Base64;
		} else
		// not known yet, may be token, verbatim, Quoted with length spec,
		// Hex with length spec, Base64 with length spec
		{
			ArrayList<Byte> datalist = new ArrayList<Byte>();
			int numbytes = 0;
			while (c >= '0' && c <= '9') {
				datalist.add(new Byte((byte) c));
				numbytes = numbytes * 10 + (c - '0');
				c = in.read();
			}
			if (c == ':' && !datalist.isEmpty()) // verbatim
			{
				for (int i = 0; i < numbytes; i++) {
					c = in.read();
					if (c < 0)
						throw new TreeParserException(
								"unexpected end of stream in verbatim encoding",
								true, false);
					out.write(c);
				}
				return Encoding.Verbatim;
			} else if (c == '"') // Quoted with length mark
			{
				int len = decodeQuoted(in, out);
				if (numbytes != len)
					throw new TreeParserException(
							"given length of quoted string encoded data does not match the actual size");

				return Encoding.Quoted;
			} else if (c == '#') // Hex with length mark
			{
				int len = decodeHex(in, out);
				if (numbytes != len)
					throw new TreeParserException(
							"given length of Hex encoded data does not match the actual size");

				return Encoding.Hex;
			} else if (c == '|') // Base64 with length mark
			{
				int len = decodeBase64(in, out);
				if (len != numbytes)
					throw new TreeParserException(
							"given length of Base64 encoded data does not match the actual size");
				return Encoding.Base64;
			} else
			// token
			{
				for (Byte b : datalist)
					out.write(b.intValue());
				int bytesWritten = 0;
				while (c >= 0 && !isWhitespace((byte) c) && c != ')'
						&& c != '(' /* && c != '[' && c != ']' */) {
					out.write(c);
					bytesWritten++;
					c = in.read();
				}
				if (c >= 0)
					in.undo();

				if (datalist.size() == 0 && bytesWritten == 0)
					throw new TreeParserException("illegal character " + c
							+ " at begin of token");

				return Encoding.Token;
			}
		}
	}

	/**
	 * auxiliary; decode following quoted string to byte array (includes reading
	 * of final '"')
	 * 
	 * @param in
	 *            input stream to read from
	 * @return resulting byte array
	 * @throws TreeParserException
	 *             an error occurred while parsing (illegal characters)
	 * @throws IOException
	 *             Exception while reading from input stream
	 */
	private static int decodeQuoted(UndoInputStream in, OutputStream out)
			throws IOException, TreeParserException {
		int c;
		int bytesWritten = 0;
		c = in.read();
		while (c != '\"') {
			if (c == -1)
				throw new TreeParserException("unexpected end of input stream",
						true, false);
			if (c == '\\') {
				c = in.read();
				if (c == -1)
					throw new TreeParserException(
							"unexpected end of input stream", true, false);
				int val = 0;
				switch (c) {
				case 'n':
					out.write('\n');
					bytesWritten++;
					break;
				case 'r':
					out.write('\r');
					bytesWritten++;
					break;
				case 'b':
					out.write('\b');
					bytesWritten++;
					break;
				case 't':
					out.write('\t');
					bytesWritten++;
					break;
				case 'v':
					out.write(0xB);
					bytesWritten++;
					break;
				case 'f':
					out.write('\f');
					bytesWritten++;
					break;
				case '\"':
					out.write('\"');
					bytesWritten++;
					break;
				case '\'':
					out.write('\'');
					bytesWritten++;
					break;
				case '\\':
					out.write('\\');
					bytesWritten++;
					break;
				case '\n':
					if (in.peek() == '\r')
						in.read();
					break;
				case '\r':
					if (in.peek() == '\n')
						in.read();
					break;
				case 'x':
					val = 0;
					c = in.read();
					if (c >= '0' && c <= '9')
						val += (c - '0') * 16;
					else if (c >= 'A' && c <= 'F')
						val += (c - 'A' + 10) * 16;
					else if (c >= 'a' && c <= 'f')
						val += (c - 'a' + 10) * 16;
					else
						throw new TreeParserException(
								"illegal character in hex value (escaped in string)");

					c = in.read();
					if (c >= '0' && c <= '9')
						val += (c - '0');
					else if (c >= 'A' && c <= 'F')
						val += (c - 'A' + 10);
					else if (c >= 'a' && c <= 'f')
						val += (c - 'a' + 10);
					else
						throw new TreeParserException(
								"illegal character in hex value (escaped in string)");

					out.write(val);
					bytesWritten++;
					break;
				default:
					val = 0;
					if (c >= '0' && c <= '9')
						val += (c - '0') * 100;
					else
						throw new TreeParserException(
								"illegal escape character");

					c = in.read();
					if (c >= '0' && c <= '9')
						val += (c - '0') * 10;
					else
						throw new TreeParserException(
								"illegal character in decimal value (escaped in string)");

					c = in.read();
					if (c >= '0' && c <= '9')
						val += (c - '0');
					else
						throw new TreeParserException(
								"illegal character in decimal value (escaped in string)");

					out.write(val);
					bytesWritten++;
				}
			} else {
				out.write(c);
				bytesWritten++;
			}
			c = in.read();
		}
		return bytesWritten;
	}

	/**
	 * auxiliary; decode following hexadecimal string to byte array (includes
	 * reading of final '#')
	 * 
	 * @param in
	 *            input stream to read from
	 * @param out
	 *            output stream to write data to
	 * @return number of bytes written to output
	 * @throws TreeParserException
	 *             an error occurred while parsing (illegal characters)
	 * @throws IOException
	 *             Exception while reading from input stream
	 */
	private static int decodeHex(UndoInputStream in, OutputStream out)
			throws IOException, TreeParserException {
		int c;
		skipWhitespaces(in);
		c = in.read();
		int bytesWritten = 0;
		while (c != '#') {
			if (c == -1)
				throw new TreeParserException("unexpected end of input stream",
						true, false);
			int val = 0;
			if (c >= '0' && c <= '9')
				val += (c - '0') * 16;
			else if (c >= 'A' && c <= 'F')
				val += (c - 'A' + 10) * 16;
			else if (c >= 'a' && c <= 'f')
				val += (c - 'a' + 10) * 16;
			else
				throw new TreeParserException("illegal character in hex value");

			skipWhitespaces(in);
			c = in.read();
			if (c >= '0' && c <= '9')
				val += (c - '0');
			else if (c >= 'A' && c <= 'F')
				val += (c - 'A' + 10);
			else if (c >= 'a' && c <= 'f')
				val += (c - 'a' + 10);
			else
				throw new TreeParserException("illegal character in hex value");

			out.write(val);
			bytesWritten++;
			skipWhitespaces(in);
			c = in.read();
		}
		return bytesWritten;
	}

	/**
	 * auxiliary; checks if given byte is a whitespace character (as defined in
	 * S-Expression draft)
	 * 
	 * @param c
	 *            byte to check
	 * @return true, if given byte is an whitespace character, else false
	 */
	public static boolean isWhitespace(byte c) {
		if (c == ' ' || c == '\t' || c == '\r' || c == '\n' || c == '\f'
				|| c == 0xB /* vertical tab */)
			return true;
		return false;
	}

	/**
	 * auxiliary; skips following whitespaces
	 * 
	 * @param in
	 *            input stream to skip whitespaces in
	 * @throws IOException
	 *             Exception while reading from input stream
	 */
	private static void skipWhitespaces(UndoInputStream in) throws IOException {
		int c;
		do {
			c = in.read();
		} while (isWhitespace((byte) c));
		if (c != -1)
			in.undo();
	}

	// Mapping table from 6-bit nibbles to Base64 characters.
	private static byte[] map1 = new byte[64];
	static {
		int i = 0;
		for (byte c = 'A'; c <= 'Z'; c++)
			map1[i++] = c;
		for (byte c = 'a'; c <= 'z'; c++)
			map1[i++] = c;
		for (byte c = '0'; c <= '9'; c++)
			map1[i++] = c;
		map1[i++] = '+';
		map1[i++] = '/';
	}

	// Mapping table from Base64 characters to 6-bit nibbles.
	private static byte[] map2 = new byte[256];
	static {
		for (int i = 0; i < map2.length; i++)
			map2[i] = -1;
		for (int i = 0; i < 64; i++)
			map2[map1[i]] = (byte) i;
	}

	/**
	 * auxiliary; checks if byte array contains given byte
	 * 
	 * @param b
	 *            byte to check
	 * @param data
	 *            byte array to search in
	 * @return true, if found, else false
	 */
	// private static boolean isInArray(byte b, byte[] data) {
	// for (int i = 0; i < data.length; i++)
	// if (b == data[i])
	// return true;
	// return false;
	// }

	/**
	 * auxiliary, reads following base64 characters
	 * 
	 * @param in
	 *            input stream to read base64 characters from
	 * @return List of read base64 characters
	 * @throws IOException
	 *             Exception while reading from input stream
	 */
	// private static ArrayList<Byte> readBase64(UndoInputStream in)
	// throws IOException {
	// ArrayList<Byte> datalist = new ArrayList<Byte>();
	// skipWhitespaces(in);
	// int c = in.peek();
	// while (c >= 0 && isInArray((byte) c, map1)) {
	// in.read();
	// datalist.add(new Byte((byte) c));
	// skipWhitespaces(in);
	// c = in.peek();
	// }
	// while (c == '=' && datalist.size() % 4 != 0) {
	// in.read();
	// datalist.add(new Byte((byte) c));
	// skipWhitespaces(in);
	// c = in.peek();
	// }
	// return datalist;
	// }

	/**
	 * decodes given list of base64 characters, for internal use with
	 * 'readBase64'
	 * 
	 * @param in
	 *            list of base64 characters to decode
	 * @return decoded byte array
	 * @throws TreeParserException
	 *             input list has invalid length or illegal character
	 */
	private static int decodeBase64(UndoInputStream in, OutputStream out)
			throws IOException, TreeParserException {
		int[] inBytes = new int[4];
		int bytesWritten = 0;

		skipWhitespaces(in);
		int c = in.read();

		while (c != '|') {
			int numBytes = 0;
			while (c != '|' && numBytes < 4) {
				if (c == -1)
					throw new TreeParserException(
							"unexpected end of input stream", true, false);
				if (c != '=') {
					if (map2[c] == -1)
						throw new TreeParserException("invalid character "
								+ ((char) c) + " in Base64 encoded data");
					inBytes[numBytes++] = map2[c];
				}
				skipWhitespaces(in);
				c = in.read();
			}
			if (numBytes == 1)
				throw new TreeParserException(
						"Length of Base64 encoded input string is invalid (1 mod 4).");
			if (numBytes > 0) {
				out.write((inBytes[0] << 2) | (inBytes[1] >>> 4));
				bytesWritten++;
			}
			if (numBytes > 2) {
				out.write(((inBytes[1]) << 4) | (inBytes[2] >>> 2));
				bytesWritten++;
			}
			if (numBytes > 3) {
				out.write(((inBytes[2] & 3) << 6) | inBytes[3]);
				bytesWritten++;
			}
		}
		return bytesWritten;

		// if (in.size() % 4 == 1)
		// throw new TreeParserException(
		// "Length of Base64 encoded input string is invalid (1 mod 4).");
		// while (in.size() % 4 != 0)
		// in.add(new Byte((byte) '='));
		// int iLen = in.size();
		//
		// while (iLen > 0 && in.get(iLen - 1).byteValue() == '=')
		// iLen--;
		// int oLen = (iLen * 3) / 4;
		// byte[] out = new byte[oLen];
		// int ip = 0;
		// int op = 0;
		// while (ip < iLen) {
		// int i0 = in.get(ip++).intValue();
		// int i1 = in.get(ip++).intValue();
		// int i2 = ip < iLen ? in.get(ip++).intValue() : 'A';
		// int i3 = ip < iLen ? in.get(ip++).intValue() : 'A';
		// if (i0 > 127 || i1 > 127 || i2 > 127 || i3 > 127)
		// throw new TreeParserException(
		// "Illegal character in Base64 encoded data.");
		// int b0 = map2[i0];
		// int b1 = map2[i1];
		// int b2 = map2[i2];
		// int b3 = map2[i3];
		// if (b0 < 0 || b1 < 0 || b2 < 0 || b3 < 0)
		// throw new TreeParserException(
		// "Illegal character in Base64 encoded data.");
		// int o0 = (b0 << 2) | (b1 >>> 4);
		// int o1 = ((b1 & 0xf) << 4) | (b2 >>> 2);
		// int o2 = ((b2 & 3) << 6) | b3;
		// out[op++] = (byte) o0;
		// if (op < oLen)
		// out[op++] = (byte) o1;
		// if (op < oLen)
		// out[op++] = (byte) o2;
		// }
		// return out;
	}

	@Override
	public Tree parseAbstractTree(byte[] in) throws TreeParserException {
		return parse(in);
	}

	@Override
	public Tree writeAbstractTree(InputStream in) throws IOException,
			TreeParserException {
		return parse(in, false);
	}
}
